package com.leetcode.算法策略相关.动态规划;

/**
 * @author: xiaomi
 * @date: 2022/5/28
 * @description: 问题描述：
 * 一个旅行者有一个最多能装M 公斤的背包，现在有 n 件物品，它们的重量分别是 W1,W2,...Wn,他们的价值分别为 C1,C2,...Cn,求旅行者能获得的最大总价值。
 * TODO
 */
public class B_01_背包问题 {

    static B_01_背包问题 action = new B_01_背包问题();


    public static void main(String[] args) {
        test1();
        test2();
        test3();
    }

    static void test1() {
        //
        int m = 10;
        int[][] goods = new int[][]{{2, 1}, {3, 3}, {4, 5}, {7, 9}};

        //1.定义dp数组：从下标为 i 的物品中取放入 容量为j 的背包，价值总和
        int[][] dp = new int[goods.length][m + 1];
        //2.初始化
        dp[0][2] = 1;
        for (int j = 3; j <= m; j++) {
            dp[0][j] = 1;
        }
        //int i = 0; i < 4; i++
        for (int i = 1; i < 4; i++) {
            for (int j = 0; j <= m; j++) {
                if (j >= goods[i][0]) {
                    //剩下的容量允许放入 good[i] 的重量时
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - goods[i][0]] + goods[i][1]);
                } else {
                    //只能选择不放
                    dp[i][j] = dp[i - 1][j];
                }

            }
        }
        int max = dp[goods.length - 1][m];

        //System.out.println("res = " + res);
    }

    static void test2() {
        //

        //System.out.println("res = " + res);
    }

    static void test3() {
        //

        //System.out.println("res = " + res);
    }
}
